# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/12 14:43 
"""

"""
给定⼀个整数数组 nums ，找到⼀个具有最⼤和的连续⼦数组（⼦数组最少包含⼀个元素），返回其最
⼤和。

题⽬要求输出数组中某个区间内数字之和最⼤的那个值。 dp[i] 表示 [0,i] 区间内各个⼦区间
和的最⼤值，状态转移⽅程是 dp[i] = nums[i] + dp[i-1] (dp[i-1] > 0) ， dp[i] =
nums[i] (dp[i-1] ≤ 0) 。

"""


class Solution:
    def maxSubArray(self, nums):
        for i in range(1, len(nums)):
            nums[i] = nums[i] + max(nums[i - 1], 0)
        return max(nums)